\section{Lineárna a diferenciálna kryptoanalýza}

Vitajte v dnešnej časti telenovely Krypto II. V minulom dieli sme
hovorili o odolnosti symetrických šifier. Dnešný diel sa pozrie na
tématiku z opačnej strany -- ukážeme si snáď prvé známe útoky na DES,
ktoré boli efektívnejšie ako bruteforce útok. Tieto útoky došli v
Na symetrické šifrovanie použijeme miesto hesla $pk_a$.
90-tych rokoch, no NSA neskôr priznala, že už v 70-tych rokoch vedela
o možnosti útokov týmto spôsobom a preto bola DES šifra navrhnutá tak,
aby boli dané útoku čo najmenej možné.

Ako už názov napovedá, budeme sa najskôr baviť o lineárnej
kryptoanalýze. Ešte predtým si ale potrebujeme upresniť šifrový
algoritmus, na ktorom budeme demonštrovať základné princípy útoku.
Budeme uvažovať blokovú šifru s rovnakou dĺžkou kľúča ako šifrovaného
textu, teda funkciu $E:\{0,1\}^n \times \{0,1\}^n \mapsto \{0,1\}^n$.

Väčšina moderných šifier pracuje v krokoch -- kolách.
My si jednotlivé kolá rozdelíme na 3 fázy. Prvou bude pričítanie
kľúča.
Druhá fáza je takzvaná substitúcia, kedy sa číslo na vstupe substitujuje
nejakou bijektívnou funkciou na iné číslo.
Tretia fáza bude ``shuffle'' kedy sa len popermutujú jednotlivé bity.
Tento princíp si môžeme predstaviť ako plošný obvod -- pričítanie
kľúča budú realizovať operácie xor po jednotlivých bitoch.
Substitúcia bude čierna skrinka, nazveme ju S-box. No a permutácia
bitov bude len poprepájanie jednotlivých vývodov nie priamo, ale nejak
popermutovane. V naších príkladoch budeme používať šifru, ktorá je
znázornená na obrázku \ref{fig:cipher}.

\begin{figure}[h]
    \centering
    \includegraphics[scale=0.7]{img/13/cipher.1.mps}
    \label{fig:cipher}
    \caption{Nákres šifry}
\end{figure}

Čo sa týka operácie ``shuffle'', je jednoduchá a symetrická, konkrétne
bity prvého (sprava) S-boxu pošle na najnižšie bity S-boxov ďalšieho kola,
bity druhého S-boxu pošle na druhé najnižšie bity S-boxov ďalšieho
kola atď. Špeciálne v poslednom kole vynechávame shuffle, pretože je
to zbytočné -- z hľadiska bezpečnosti nič nepridá a šifrovací
algoritmus je rýchlejší bez tejto operácie. Na definovanie celej šifry
nám ešte ostáva popísať substitučnú čiernu skrinku.
S-box (substitučný box) sme si zvolili nasledovne:
\begin{equation*}
    Sbox:[0,1,2,\dots,15] \mapsto
    [10, 5, 0, 13, 14, 11, 4, 6, 9, 2, 12, 3, 7, 1, 8, 15]
\end{equation*}

\begin{poznamka}
    Naša šifra je zhodná so šifrou prezentovanou na prednáške až na
    jeden drobný detail. Rozhodli sme sa číslovať bity na vstupe
    sprava doľava narozdiel od prednášky. Dôvod je totiž ten, že bity
    S-boxu sú číslované sprava doľava a pôvodne to spôsobovalo chaos
    keďže boli číslované opačným smerom ako bity vstupu. Táto
    transformácia sa ale nezaobišla bez následkov. Aby sme zachovali
    obrázky (a tiež lineárne kombinácie, ktoré potrebujeme), museli
    sme zmeniť funkciu Sboxu (vymeniť poradie bitov na vstupe a
    takisto aj na výstupe).
    Pôvodný Sbox z prednášky je
    \begin{equation*}
    SboxOrig:[0,1,2,\dots,15] \mapsto
    [5, 9, 7, 14, 0, 3, 2, 1, 10, 4, 13, 8, 11, 12, 6, 15]
    \end{equation*}
\end{poznamka}

Šifra šifruje naraz 16 bitov otvoreného textu a 
veľkosť kľúča k šifre je $5*16=80\unit{bitov}$.
Toto sa samo o sebe zdá ako pomerne odolné voči generickému útoku
hrubou silou. Na druhej strane, počet rôznych otvorených textov je iba
65536, čo nie je zrovna veľmi bezpečné. Šifra by sa ale ľahko dala
rozšíriť o ďalšie bity veľmi podobnou konštrukciou.

Keď sme si už predstavili šifru, na ktorú budeme v zvyšku tejto
kapitoly útočiť, bolo by načase predstaviť si aj našich bojovníkov,
ktorí majú ambíciu jej to rozdať.

\subsection{Lineárna kryptoanalýza}

Všeobecne pri kryptoanalýze sa budeme snažiť nájsť štatistické odchýlky
správania sa šifry od náhodnej funkcie.
V tomto konkrétnom prípade to budú štatistické odchýlky
pre lineárnej kombináciu vstupov a výstupov.
Presnejšie povedané, uvažujme vstupné bity
$in_{a_1},in_{a_2},\dots,in_{a_n}$ a výstupné bity
$out_{k,b_1},out_{k,b_2},\dots,out_{k,b_m}$ kde $k$ je šifrovací kľúč.

Očakávaná pravdepodobnosť, že pre náhodný kľúč $k$ bude platiť
\begin{equation}
    \label{eq:lin_approx}
    \bigoplus_{i=1}^n in_{a_i} == \bigoplus_{j=1}^{m} out_{k,b_j}
\end{equation}
je v prípade náhodného orákula presne $1/2$. Cieľom kryptoanalýzy bude
preto nájsť takú lineárnu kombináciu vstupov, pre ktorú je táto
pravdepodobnosť čím viac rôzna od $1/2$. Vtedy totiž túto nerovnováhu
dokážeme využiť v náš prospech a dokážeme efektívnejsie lámať kľúče.
Na tento útok bude stačiť, ak si nazhromaždíme dostatočne veľký počet
dvojíc $\langle plaintext, ciphertext \rangle$.

V prvom rade, mali by sme si
uvedomiť, že nám stačí skúmať S-boxy. Ostatné časti šifry sú totiž
lineárne. Ďalej urobíme predpoklad, že dané S-boxy sú nezávislé. To
nám umožní sústrediť sa na analýzu jedného S-boxu a následne budeme
vedieť skladať pravdepodobnosti pre celú šifru.

Základom analýzy jedného S-boxu je takzvaná lineárna aproximačná
tabuľka, v ktorej si zobrazíme lineárne závislosti medzi vstupmi a
výstupmi S-boxu.
Hodnota políčka tejto tabuľky bude označovať balanciu,
koľko sme mali v rovnici \ref{eq:lin_approx} zhôd verzus počet nezhôd.
Matematicky by sa to dalo zapísať ako
\begin{equation*}
    table[lin_{in},lin_{out}] = \sum_{x \in \{0,1\}^n} (-1)^{
        x \cdot lin_{in} \oplus S(x) \cdot lin_{out}}
\end{equation*}
kde pod $lin_{in},lin_{out}$ sme označili vektory znamenajúce
prítomnosť jednotlivých vstupov/výstupov v lineárnej kombinácii
a operáciou $\cdot$ sme označili skalárny súčin keď sa pozrieme na
argumenty ako na postupnosti bitov. Poznamenajme, že tento skalárny
súčin je tiež v poli $Z_2$.

Lineárna aproximačná tabuľka pre náš S-box je zobrazená v tabuľke
\ref{tab:lat}.

\input{tex/kryptoanalyza/lat.tex}
Za povšimnutia stoja niektoré vlastnosti tabuľky. Prvou je
$table[0,0] = 16$, čo je očakávané. Ak totiž nevyberieme žiadne bity,
tak očakávame $0==0$ so 100\%-tnou pravdepodobnosťou.
Naopak, všetky políčka $[x,y]$, pre ktoré $table[x,y]=0$ budú
nepoužiteľné v našej analýze. Vtedy je totiž počet zhôd a nezhôd
rovnaký a teda pravdepodobnosť je presne $1/2$. Naším cieľom bude
pozbierať vhodné lineárne aproximácie pre S-boxy a poskladať z nich
lineárnu kombináciu pre celú šifru okrem posledného kola.
Túto kombináciu následne použijeme na štatistické testovanie
vhodnosti jednotlivých šifrovacích kľúčov posledného kola. Presnejšie
si to popíšeme v príkladoch, teraz sa budeme venovať leme na skladanie
pravdepodobností.

\todo{suvis tabulky s pravdepodobnostami}
\begin{lema}[Piling-up lema]
    \todo{znenie a dokaz}
\end{lema}


\begin{priklad}
    \label{prikl:lin1}

    Aby sme neostali iba pri teoretických obkecoch, ukážeme si
    prakticky ako vyzerá a dopadne kryptoanalýza. Uvažujme najskôr
    lineárnu kombináciu vstupných bitov $9,10,12,15$ a výstupných
    bitov $0,2,8,10$. Presnejšie ktoré lineárne kombinácie budeme
    uvažovať po ceste si čitateľ môže pozrieť na obrázku
    \ref{fig:lin1}. Nateraz nás bude zaujímať hlavne to, že na
    vstupe aj na výstupe máme relatívne malý počet použitých S-boxov.
    Tým pádom vie byť kryptoanalýza úspešná (lebo nám stačí preveriť
    kľúče na malej kombinácii výstupov).

    Pre každý S-box si vypočítame balanciu pravdepodobnosti, ktorú
    očakávame. Môžeme si všimnúť napríklad, že špeciálne pre S-boxy,
    ktoré nemajú vyznačený žiadny pin je táto balancia 0.5 pretože je
    100\%-ná pravdepodobnosť, že $0 = 0$ (Lineárna kombinácia vstupov
    sa rovná lineárnej kombinácii výstupov).

    Následne budeme dávať tieto pravdepodobnosti dokopy. Aby sme to
    mohli spraviť, budeme uvažovať, že tieto pravdepodobnosti sú
    nezávislé. Toto je síce evidentne nepravdivý predpoklad, ale
    výrazne zjednodušuje analýzu. Môžeme totiž použiť piling-up lemu
    na skladanie týchto pravdepodobností (teda, v našom prípade skôr
    balancií). Takto získame pre každý round šifry (s výnimkou
    posledného) balanciu príslušnej
    lineárnej kombinácie. Opäť použijeme piling-up lemu a môžeme
    vypočítať balanciu lineárnej kombinácie vstupu a výstupu z
    predposledného kola šifry. No a tento výstup budeme štatisticky
    testovať pre rôzne kľúče a kľúč, ktorý bude najbližšie k
    vypočítanej hodnote budeme považovať za správny.\footnote{V
    skutočnosti to nie je také jednoduché, hlavne, ak výsledky analýzy
    nie sú veľme jednoznačné. Vtedy by sme mohli určiť pravdepodobnosti
    pre jednotlivé časti kľúča a následne vyskúšať bruteforce attack
    v poradí podľa klesajúcej pravdepodobnosti celého kľúča.}

    \begin{figure}[H]
        \centering
        \includegraphics[scale=0.7]{img/13/lin.1.mps}
        \caption{Lineárna aproximácia v príklade \ref{prikl:lin1}}
    \end{figure}


    Teoretická analýza je teda nasledovná:
    \input{tex/kryptoanalyza/lanalyza1.tex}

    Po teoretickej stránke máme teda útok zvládnutý. Ešte ostáva
    ukázať, ako to funguje v praxi. Zašifrovali sme sadu náhodných
    textov tým istým náhodným kľúčom a následne sme skúšali hádať časť
    podkľúča $key_5$. Algoritmus bol jednoduchý -- pre každý možný
    kľúč (resp. tú časť kľúča, o ktorej máme šancu niečo zistiť, v
    našom prípade S-boxy so vstupmi 0-3, 8-11) sme pomocou všetkých
    otvorených a šifrových textov vypočítali pravdepodobnosť (a teda
    aj balanciu) pre daný kľúč. Následne sme ako kľúč zvolili ten,
    ktorý mal najväčšiu balanciu v absolútnej hodnote. V tabuľke
    \todo{ref} sú ukázané výsledky na sade 1000 dvojíc otvoreného a
    šifrového textu.
    \input{tex/kryptoanalyza/lattack1.tex}
\end{priklad}

\begin{priklad}
    \label{prikl:lin2}
    V druhom príklade sme si zvolili inú lineárnu aproximáciu. Toto
    nás môže doviesť k inej časti kľúča, ktorý by sme chceli zlomiť.
    Samozrejme, hľadanie vhodnej lineárnej aproximácie je veľmi
    netriviálna (a iba na ňom stojí celá táto kryptoanalýza). V našom
    prípade sme opäť našli veľmi jednoduchú (t.j. málo použitých
    ciest) kombináciu.
    \begin{figure}[H]
        \centering
        \includegraphics[scale=0.7]{img/13/lin.2.mps}
        \caption{Lineárna aproximácia v príklade \ref{prikl:lin2}}
    \end{figure}
    Opäť si najskôr teoreticky analyzujeme situáciu. Tak ako v
    predchádzajúcom prípade, aj teraz budeme uvažovať, že jednotlivé
    pravdepodobnosti sú úplne nezávislé.
    \input{tex/kryptoanalyza/lanalyza2.tex}

    Čo sa týka praktických výsledkov, dajú sa nájsť v tabuľke
    \todo{ref}. Môžeme si všimnúť, že hlavne v prvom prípade je
    výsledok pomerne nejednoznačný. Na úspešnú kryptoanalýzu by bolo
    preto potrebné mať zrejme viac údajov, alebo, na druhej strane,
    previesť spomínanú variantu bruteforce útoku s preberaním
    pravdepodobnejších kľúčov $key_5$ skôr. Za zmienku navyše stojí,
    že okrem časti kľúča $key_5$ vieme touto metódou získať ja
    lineárnu kombináciu (xor) niektorých bitov kľúčov $key_1, \dots,
    key_4$. Môžeme sa totiž pozrieť na to, či daná balancia vyšla
    kladná alebo záporná a rozhodnúť sa, či to vychádza ako očakávaná
    balancia alebo presne naopak.

    \input{tex/kryptoanalyza/lattack2.tex}
\end{priklad}


\subsection{Diferenciálna kryptoanalýza}
Princíp diferenciálnej kryptoanalýzy je veľmi príbuzný 
už preberanej lineárnej analýzy. Opäť budeme analyzovať
štatistické odchýlky šifry od náhodného zobrazenia.
Tentoraz všal nebudeme uvažovať lineárnu analýzu vstupov,
ale niečo zložitejšie. Ak si vezmeme 2 otvorené texty, ktoré sa líšia
na niektorých pozíciach, bude nás zaujímať, ako sa budú líšiť na
niektorých výstupných pozíciach. V prípade, že máme iba zoznam
otvorených a šifrových textov, môže to spôsobovať problémy, pretože
nie je jednoduché nájsť vhodnú dvojicu otvorených textov.
Preto sa tento útok zvyčajne vyskytuje v podobe CPA, t.j. útočník si
môže voliť otvorené texty a používať svoju obeť ako orákulum na
šifrové texty. Praktickými aspektami tohoto útoku sa nebudeme veľmi
zaoberať, je však evidentné, že presvedčiť svoju obeť zašifrovať
tisícky náhodných otvorených textov nemusí byť práve najjednoduchšie.

Vráťme sa ale späť ku kryptoanalýze. Podobne ako minule, aj teraz si
spravíme tabuľku, ktorá bude popisovať jeden S-box. 
Riadky tabuľky budú reprezentovať diferenciu (xor) medzi vstupmi do
S-boxu, stĺpce budú reprezentovať diferenciu medzi výstupmi. Každé
políčko tabuľky bude obsahovať počet tých vstupov pre S-box, pre ktorý
je diferencia medzi jeho výstupom a výstupom zmeneným podľa vstupnej
diferencie práve výstupná diferencia. Inak povedané
\begin{equation*}
    table[d_{in},d_{out}] = \sum_{x=0}^{max\_input-1}
        \left[Sbox(x) \oplus Sbox(x \oplus d_{in}) == d_{out}\right]
\end{equation*}
Pre náš S-box sa dajú nájsť konkrétne hodnoty v tabuľke \ref{tab:dif}
\input{tex/kryptoanalyza/dif.tex}

Môžeme si všimnúť niekoľko vlastností tabuľky.
Prvou je, že $table[0,0]=16$, čo je pochopiteľné -- ak uvažujeme dva
rovnaké otvorené texty, šifrové texty budú tiež rovnaké bez ohľadu na
otvorený text. Ďalej, súčet v riadku je vždy 16, čo je opäť triviálne
nahliadnuteľné. Trochu menej triviálne je to isté pozorovanie o
stĺpcoch tabuľky -- v tomto prípade môžeme argumentovať napríklad tým,
že sa na celú situáciu budeme pozerať z opačnej strany (vymeníme
otvorené a šifrové texty) a naša šifra bude pôvodná dešifrovacia funkcia.

Každé políčko tabuľky nám narozdiel od lineárnej kryptoanalýzy
neukazuje balanciu pravdepodobnosti ale priamo pravdepodobnosť. Teda,
presnejšie povedané, políčko vydelené počtom všetkých možných vstupov
pre S-box.
Tieto pravdepodobnosti budeme opäť uvažovať, že sú nezávislé a teda
ich budeme môcť beztrestne násobiť.


\begin{priklad}
    \label{prikl:dif1}
    \begin{figure}[H]
        \centering
        \includegraphics[scale=0.7]{img/13/dif.1.mps}
        \caption{Diferenciálna analýza v príklade \ref{prikl:dif1}}
    \end{figure}

    \noindent
    \input{tex/kryptoanalyza/danalyza1.tex}
    \input{tex/kryptoanalyza/dattack1.tex}
\end{priklad}

\begin{priklad}
    \label{prikl:dif2}
    \begin{figure}[H]
        \centering
        \includegraphics[scale=0.7]{img/13/dif.2.mps}
        \caption{Diferenciálna analýza v príklade \ref{prikl:dif2}}
    \end{figure}

    \noindent
    \input{tex/kryptoanalyza/danalyza2.tex}
    \input{tex/kryptoanalyza/dattack2.tex}
\end{priklad}

\begin{priklad}
    \label{prikl:dif3}
    \begin{figure}[H]
        \centering
        \includegraphics[scale=0.7]{img/13/dif.3.mps}
        \caption{Diferenciálna analýza v príklade \ref{prikl:dif3}}
    \end{figure}

    \noindent
    \input{tex/kryptoanalyza/danalyza3.tex}
    \input{tex/kryptoanalyza/dattack3.tex}
\end{priklad}
